The present invention relates to a method for morphing, in an object space, the outlines of characters or figures consisting of straight lines and curves.
Morphing, which is short for metamorphosing, is an animation technique involving moving a control point set on an image, so that image can be smoothly and seamlessly transformed into another.
A conventional technique for using morphing to transform a character on a display is disclosed in reference document 1, xe2x80x9cAdvanced Animation and Rendering Techniques,xe2x80x9d Alan Watt and Mark Watt, Addison-Wesley, 1992, pp. 413. In reference document 1, a method is described whereby characters defined using Bezier curves are transformed by linearly interpolating control points on the curves. As an actual operating example, in the document the transformation of the character xe2x80x9cExe2x80x9d into the character xe2x80x9cZxe2x80x9d is described.
However, the technique disclosed in reference document 1 is not generally applicable. It cannot be applied for a general outline font, such as a True Type font, that consists of line segments and Bezier curves. Furthermore, the technique presented in the document handles only characters for which the outline consists of a single line, such as xe2x80x9cExe2x80x9d or xe2x80x9cZ.xe2x80x9d That is, the technique in reference document 1 cannot be applied for characters for which the outlines consist of multiple lines, including characters containing internal spaces, such as xe2x80x9cAxe2x80x9d or B,xe2x80x9d or characters, such as Chinese characters, for which many strokes are used.
Techniques for using morphing to transform two-dimensional outline curves are also disclosed in: reference document 2, xe2x80x9cA Physically Based Approach to 2-D Shape Blending,xe2x80x9d T. W. Sederberg, et al., SIGGRAPH Proceeding, 1992, pp. 25-34; reference document 3, xe2x80x9c2-D Shape Blending: An Intrinsic Solution to the Vertex Path Problem,xe2x80x9d T. W. Sederberg, et al., SIGGRAPH Proceeding, 1993, pp. 15-18; reference document 4, xe2x80x9cA Fuzzy Approach to Digital Image Warping,xe2x80x9d Y. Zhang, 1996, July, pp. 34-41; and reference document 5, xe2x80x9cSelf-intersection Elimination In Metamorphosis of Two-dimensional Curves,xe2x80x9d T. Samoilov and G. Elber, The Visual Computer, 1988, Vol. 14, pp. 415-428.
The technique disclosed in reference documents 2 and 3 employs an algorithm whereby an outline consisting of straight lines (sides), such as linear lines or polylines, is transformed by using, as parameters, angles formed by adjacent sides and the lengths of these sides. However, it is difficult for this technique to perform the morphing of a figure, such as a character, having many raised and recessed portions.
The technique disclosed in reference document 4 is a method for distorting a two-dimensional polygonal image to perform morphing in an image space. However, since this technique processes an image in the image space, the outline has jaggy contours. Furthermore, the size of a figure cannot be enlarged or reduced (morphing cannot be performed using an arbitrary scale).
Reference document 5 discloses two algorithms to prevent self-intersection during the morphing process. However, the premise is that two two-dimensional closed curves are similar in phase so that figures that can avoid self-intersection during transformation are limited.
As is described above, it is difficult to employ the known morphing techniques to transform the outlines of complicated figures, such as characters.
When the process is performed in an image space, as disclosed in the referenced document 4, the outline of the image is jaggy, and a satisfactory appearance cannot be obtained. Further, since an arbitrary scale cannot be used only limited visual effects are possible.
When the image processing is performed in object space using vectors, the types and shapes of target figures for which the processing can be performed are limited. In the method of reference document 1 only figures that have outlines consisting of single lines can be handled. With the method of reference documents 2 and 3, figures having many raised and recessed portions cannot be handled.
In addition, it is important self-intersection in an outline be avoided because the internal space of the outline may not satisfactorily be solidly painted with a specific color. The technique disclosed in reference document 5 is not generally applicable because the figures for which self-intersection can be avoided are limited.
Therefore it is one object of the present invention to perform morphing, in a vector space, for the outlines for various types and shapes of figures.
It is a further object of the present invention to perform morphing for a figure that consists of a plurality of outlines.
It is still a further object of the present invention to perform morphing for a figure having raised and recessed portions, while preventing self-intersection.
It is another object of the present invention to perform morphing for a character or for a character string on a computer display device.
According to the present invention, a morphing processing apparatus, which performs a morphing process for the smooth transformation of one figure into another, comprises: an outline extractor, for receiving two target figures for the morphing process and for extracting a set of outlines for each of the target figures; an outline arrangement unit, for retaining one specific outline of each of the two sets of outlines extracted for the target figures and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target figures that are retained by the outline arrangement unit in order to prevent self-intersection during the morphing process; and a morphing execution unit, for performing the morphing process in response to the progress made by the smoothing process performed by the smoothing processor.
The outline arrangement unit includes: an outline tree generator, for generating an outline tree having nodes that correspond to the outlines that are extracted for the two target figures by the outline extractor and that reflect the relationship of the outlines; and an outline tree arrangement unit, for retaining only one specific node, of those nodes of the outline tree that are generated by the outline tree generator, for each of the figures and for deleting the other nodes in accordance with a predetermined rule, wherein the smoothing processor performs the smoothing process for each outline that corresponds to one of the nodes that are retained as a result of the process performed by the outline arrangement unit. This arrangement is preferable because a desired outline can be retained by designating the node of the outline tree, while taking the structure of the outline tree into account. Further, as will be described later, information concerning a bounding box that encloses an outline is stored in the node of the outline tree. In this case, a node for which the size of the bounding box is the maximum may be retained.
Furthermore, the outline tree generator receives the outlines of the target figures that are extracted by the outline extractor, designates, for each of the outlines, a bounding box that encloses the pertinent outline, and generates an outline tree based on the relationship existing between the bounding boxes. This arrangement is preferable because the relationship of the outlines that constitute the target figure will be readily apparent. While an arbitrary shape can be selected for a bounding box, a rectangular shape is easy to handle when a target figure is a character.
In addition, when a curve is included in the outlines of the target figures, the outline extractor divides the curve into line segments and performs segment approximation. Therefore, the outline can be treated as a polygon, and the process can be generalized so that it can be performed regardless of the shape of the target figure.
Further, the outline extractor receives, as a target figure, an outline font character and extracts the outline of the character. As a result, excellent visual effects can be provided for the display of a text document. Moreover, if the outline of a bit-mapped font can be extracted as a pre-process, this can also be employed as a morphing target.
However, as a target figure for the extraction of an outline, the outline extractor normally receives a true type font character. Thus, since morphing can be performed for fonts that are widely used by personal computers, this technique is more commonly employed.
As the smoothing process, the smoothing processor performs Laplacian smoothing for the outline. Laplacian smoothing is merely an example smoothing process, however, and another process may be employed.
The morphing execution unit includes: a sequence generator for generating a sequence file in which the outlines obtained by the smoothing processor are arranged along a time parameter; and a morphing execution section for performing morphing based on the sequence file obtained by the sequence generator. This arrangement is superior because not only morphing where self-intersection does not occur can be implemented by tracing the sequence file, but also morphing in the opposite direction can be easily performed by tracing the sequence file backward. When self-intersection does not occur during the morphing process, even though the smoothing process is not performed, the sequence file can be formed of only the two outlines that are retained by the outline arrangement unit.
Further, according to the present invention, a morphing method, for smoothly transforming two figures from one to the other by morphing, comprises: an outline extraction step of extracting, as line segments, outlines of two target figures for a morphing process; an outline tree generation step of generating an outline that has nodes corresponding to the outlines extracted for each of the target figures, and that reflects the relationship of the outlines; a node deleting step of retaining one specific node from among the nodes of the outline tree generated for each of the target figures, and deleting the other nodes; a vertex count matching step of matching the number of vertexes of two outlines that correspond to the nodes that are respectively retained in the outline trees for the two target figures; a smoothing step of performing a smoothing process for the two outlines for which the number of vertexes match, so that self-intersection does not occur during the morphing process; a sequence file generation step of generating a sequence file along a time parameter for the outlines obtained in the smoothing process; and a morphing step of performing morphing based on the sequence file, and of displaying the results.
The outline tree generation step includes the steps of: designating, for each of the outlines that constitute the target figures, a bounding box that encloses the pertinent outline; generating a bounding box that can enclose each of the target figures, and generating a root node of the outline tree that corresponds to the bounding box; and selecting one of the bounding boxes respectively generated for the outlines, generating a child node that corresponds to the outline of the selected bounding box, and inserting the child node under the root node. The step of inserting the child node includes the step of: recurrently inserting the child node under the different node when the bounding box that encloses an outline that corresponds to a predetermined child node is completely included in a bonding box that encloses an outline corresponding to a different child node that has already been inserted under the root node. This arrangement is preferable because the geometrical structure of the outlines of the target figure can be reflected in the structure of the outline tree.
The node deleting step includes the steps of: determining a node to be retained in accordance with the predetermined rule; and moving, to one arbitrary point, vertexes of the outlines that correspond to the other nodes, and regarding the point as a point that is not finally displayed. Thus, the state wherein unwanted outlines are gradually removed can be displayed. While an arbitrary position can be set for a point whereat the outlines converge, it is preferable that the outlines be moved to the center of the bounding box because the display is visually well balanced.
The vertex count matching step includes the steps of: arranging vertexes of two outlines beginning at a specific position and extending around the two outlines in a constant direction; employing a parameter whose value falls within a constant range to represent coordinates of the vertexes that are rearranged; and comparing the parameters of the vertexes along the two outlines, and mutually employing the parameters of the vertexes for one of the outlines to linearly interpolate the vertexes with the other outline. At the step of employing the parameters of the vertexes to perform linear interpolation for the vertexes of the two outlines, points that correspond to the vertexes of one of the outlines are added to the other outline, and vice versa. This arrangement is superior because a new vertex obtained by linear interpolation need not be merged or sorted between the files of the two outlines.
At the smoothing step, the Laplacian smoothing is repeated for the outlines an arbitrary number of times, and when during morphing self-intersection does not occur, the Laplacian smoothing is halted. It is visually preferable that the Laplacian smoothing be halted during the process, because the target figure can be prevented from becoming substantially circular as a result of the smoothing, regardless of the original shape.
The smoothing step includes the steps of: performing a trial morphing for two outlines for which the number of vertexes match, and for confirming the occurrence or nonoccurrence of self-intersection; and repeating the Laplacian smoothing for the two outlines an arbitrary number of times when self-intersection occurs as a result of the trial morphing. The smoothing step recurrently repeats the two steps until self-intersection does not occur, even when the trail morphing is performed. This arrangement is superior because the Laplacian smoothing can be mechanically halted when self-intersection does not occur.
Further, according to the present invention, a storage medium is provided on which input means for a computer stores a computer-readable program, which permits the computer to perform: a process for inputting two target figures for morphing; a process for extracting, as line segments, outlines of the two target figures; a process for generating an outline tree that has nodes corresponding to the outlines extracted for each of the target figures, and that reflects the relationship of the outlines; a process for retaining one specific node from among the nodes of the outline tree generated for each of the target figures, and deleting the other nodes; a process for matching the number of vertexes of two outlines that correspond to the nodes that are respectively retained in the outline trees for the two target figures; a process for performing a smoothing process for the two outlines for which the number of vertexes match, so that self-intersection does not occur during the morphing process; a process for generating a sequence file along a time parameter for the outlines obtained in the smoothing process; and a process for performing morphing based on the sequence file, and of displaying the results. This arrangement is preferable because a computer into which this program is loaded can perform morphing without self-intersection occurring.
Further, according to the present invention, a program transmission apparatus comprises: storage means, for storing a program to permit a computer to perform a process for inputting two target figures for morphing, a process for extracting, as line segments, outlines of the two target figures, a process for generating an outline tree that has nodes corresponding to the outlines extracted for each of the target figures, and that reflects the relationship of the outlines, a process for retaining one specific node from among the nodes of the outline tree generated for each of the target figures, and deleting the other nodes, a process for matching the number of vertexes of two outlines that correspond to the nodes that are respectively retained in the outline trees for the two target figures, a process for performing a smoothing process for the two outlines for which the number of vertexes match, so that self-intersection does not occur during the morphing process, a process for generating a sequence file along a time parameter for the outlines obtained in the smoothing process, and a process for performing morphing based on the sequence file, and of displaying the results; and transmission means for reading the program from the storage means and for transmitting the program. With this program transmission apparatus, the technique of the present invention can be provided for a client without a storage medium, such as a CD-ROM, which is a program loading form, being required.
Furthermore, a morphing processing apparatus comprises: a calculator; and a display device for displaying the results obtained by the calculator, wherein the calculator receives, as targets, a figure string consisting of m arbitrary figures as elements and a figure string consisting of n arbitrary figures as elements, and correlates the elements of the two figure strings with each other, wherein, when the numbers of the elements of the two figure strings do not match, the calculator adds, to the figure string whose element is the shortest, circles that are not displayed on the display device and that are equivalent in number to the shortest elements, so that the circles correspond to extra elements of the other figure string, and wherein the calculator performs morphing for the elements that are correlated with each other, so as to smoothly transform one figure string into the other figure string. This arrangement is preferable because morphing can be performed for figure strings, each of which consist of multiple figures, and because general use of this technique has increased.
According to the present invention, a morphing processing apparatus can be provided that comprises: an outline extractor, for receiving two target characters for the morphing process and for extracting a set of outlines for each of the target characters; an outline arrangement unit, for retaining one specific outline of each of the two sets of outlines extracted for the target characters and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target characters that are retained by the outline arrangement unit in order to prevent self-intersection during the morphing process; and a morphing execution unit, for performing the morphing process in response to the progress made by the smoothing process performed by the smoothing processor. A target character for morphing can be defined as a character specified by character code that is used by a computer or a dedicated word processor. Thus, a character entered at a keyboard can be used unchanged to perform morphing therefor.
Further, according to the present invention, a morphing processing apparatus can be provided, which comprises: an outline extractor, for receiving two target fonts for a morphing process and for extracting a set of outlines for each of the target fonts; an outline arrangement unit, for retaining one specific outline of each of the two sets of outlines extracted for the target fonts and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target fonts that are retained by the outline arrangement unit in order to prevent self-intersection during the morphing process; and a morphing execution unit, for performing the morphing process in response to the progress made by the smoothing process performed by the smoothing processor. With this arrangement, a transformation process using morphing can also be performed for a character or a character string that is displayed with different fonts.
Furthermore, according to the present invention, a morphing processing apparatus that smoothly transforms one figure into another one comprises: an outline arrangement unit for receiving sets of outlines that respectively constitute two target figures for a morphing process, and for retaining a specific outline selected from each of the sets of outlines for the target figures and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target figures that are retained by the outline arrangement unit in order to prevent self-intersection during the morphing process; and a morphing execution unit, for performing the morphing process in response to the progress made by the smoothing process performed by the smoothing processor. With this arrangement, outline information can be obtained directly from a target figure, such as a character of an outline font, that possesses the outline information, and morphing can be performed.
In addition, according to the present invention an animation creation apparatus, for creating an animated sequence wherein one figure is smoothly transformed into another, comprises: an outline extractor, for receiving two target figures for the morphing process and for extracting a set of outlines for each of the target figures; an outline arrangement unit, for retaining one specific outline of each of the two sets of outlines extracted for the target figures and for deleting the other outlines; a smoothing processor, for performing a smoothing process for the two outlines for the target figures that are retained by the outline arrangement unit in order to prevent self-intersection when one outline is transformed to the other; and an image processor, for creating an animated sequence wherein one figure is smoothly transformed into another in response to the progress made by the smoothing process performed by the smoothing processor.